{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: coins = [1, 2, 5], amount = 11\n",
    "输出: 3 \n",
    "解释: 11 = 5 + 5 + 1\n",
    "示例 2:\n",
    "\n",
    "输入: coins = [2], amount = 3\n",
    "输出: -1\n",
    "说明:\n",
    "你可以认为每种硬币的数量是无限的。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/coin-change\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 深度搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort()\n",
    "        times = 0\n",
    "        fewest = float(\"inf\")\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(amount, coins_count):\n",
    "            nonlocal fewest, times\n",
    "            times += 1\n",
    "            if amount == 0:\n",
    "                return True\n",
    "            print(\"amount=\", amount, coins_count)\n",
    "            # elif amount < 0:\n",
    "            #     return False\n",
    "            for i in coins:\n",
    "                if amount - i >= 0:\n",
    "                    res = helper(amount - i, coins_count + 1)\n",
    "                    if res:\n",
    "                        fewest = min(fewest, coins_count+1)\n",
    "            \n",
    "        helper(amount, 0)\n",
    "        print(\"times=\", times)\n",
    "        return fewest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "amount= 11 0\namount= 10 1\namount= 9 2\namount= 8 3\namount= 7 4\namount= 6 5\namount= 5 6\namount= 4 7\namount= 3 8\namount= 2 9\namount= 1 10\namount= 1 9\namount= 2 8\namount= 3 7\namount= 1 8\namount= 4 6\namount= 2 7\namount= 1 6\namount= 5 5\namount= 3 6\namount= 1 7\namount= 2 5\namount= 6 4\namount= 4 5\namount= 2 6\namount= 1 5\namount= 3 4\namount= 7 3\namount= 5 4\namount= 3 5\namount= 2 4\namount= 4 3\namount= 8 2\namount= 6 3\namount= 4 4\namount= 1 4\namount= 3 3\namount= 5 2\namount= 9 1\namount= 7 2\namount= 5 3\namount= 2 3\namount= 4 2\namount= 6 1\namount= 1 2\ntimes= 54\n3\n"
    }
   ],
   "source": [
    "coins = [1, 2, 5]\n",
    "amount = 11\n",
    "res = Solution().coinChange(coins, amount)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用functools.lru_cache优化\n",
    "\n",
    "优化后的结果\n",
    "\n",
    "运行 54 次\n",
    "\n",
    "\n",
    "没优化的结果\n",
    "\n",
    "运行 527 次"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "找了一个说的比较好的题解\n",
    "\n",
    "假设 f(n) 代表要凑齐金额为 n 所要用的最少硬币数量，那么有：\n",
    "\n",
    "f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1\n",
    "其中 c1 ~ cn 为硬币的所有面额。\n",
    "\n",
    "假设有`[1, 2, 5]` 3种硬币\n",
    "\n",
    "那么 `f(11) = min(f(11-1), f(11-2), f(11-5)) + 1` 种最少硬币数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "看了别人的代码，又看了别人的解题思路，终于搞懂了，于是再写一遍"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 自顶向下\n",
    "import functools\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(amount):\n",
    "            if amount == 0:\n",
    "                return 0\n",
    "            return min(helper(amount-c) if amount - c >=0 else float(\"inf\") for c in coins) + 1\n",
    "        \n",
    "        res = helper(amount)\n",
    "        return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 自底向上\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        # 自底向上\n",
    "        # dp[i] 表示金额为i需要最少的硬币\n",
    "        # dp[i] = min(dp[i], dp[i - coins[j]]) j所有硬币\n",
    "        \n",
    "        dp = [float(\"inf\")] * (amount + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, amount + 1):\n",
    "            dp[i] = min(dp[i - c] if i - c >= 0 else float(\"inf\") for c in coins ) + 1\n",
    "        return dp[-1] if dp[-1] != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "唉太难了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}